package com.binaryTree;

import java.util.Stack;

public class ValidateBinarySearchTree0305_98 {
    //中序遍历

    //递归
    TreeNode max;
    public boolean isValidBST1(TreeNode root) {
        if (root == null) return true;

        boolean left = isValidBST1(root.left);
        if(!left) return false;

        if( max != null && root.val <= max.val) return false;
        max = root;

        boolean right = isValidBST1(root.right);

        return right;
    }


    //统一迭代
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        Stack<TreeNode> sta = new Stack<>();
        TreeNode pre = null;
        sta.push(root);
        while (!sta.isEmpty()){
            TreeNode node = sta.pop();
            if(node == null){
                TreeNode node1 = sta.pop();
                if(pre != null && node1.val <= pre.val) return false;
                pre = node1;
            }else {
                if(node.right != null) sta.push(node.right);
                sta.push(node);
                sta.push(null);
                if(node.left != null) sta.push(node.left);
            }
        }
        return true;
    }
}
